package ljl.alg.wangzheng_camp.round1.bfsdfs;

import java.util.*;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class _17_07_baby_name {
    
    static class semi_auto_union_find {
        public String[] trulyMostPopular(String[] names, String[] synonyms) {
            Map<String, Integer> count = new HashMap<>();
            Map<String, String> parent = new HashMap<>();
            for (String name : names) {
                int par = name.indexOf('(');
                count.put(name.substring(0, par), Integer.parseInt(name.substring(par + 1, name.length() - 1)));
            }
            for (String synonym : synonyms) {
                int coma = synonym.indexOf(',');
                String root1 = synonym.substring(1, coma);
                String root2 = synonym.substring(coma + 1, synonym.length() - 1);
                while (parent.containsKey(root1)) root1 = parent.get(root1);
                while (parent.containsKey(root2)) root2 = parent.get(root2);
                if (!root1.equals(root2)) {
                    int freq = count.getOrDefault(root1, 0) + count.getOrDefault(root2, 0);
                    String son = root1.compareTo(root2) > 0 ? root1 : root2;
                    String father = root1 == son ? root2 : root1;
                    parent.put(son, father);
                    count.remove(son);
                    count.put(father, freq);
                }
            }
            String[] res = new String[count.size()];
            int i = 0;
            for (Map.Entry<String, Integer> each : count.entrySet()) {
                res[i++] = each.getKey() + '(' + each.getValue() + ')';
            }
            return res;
        }
    }
    
    static class std_union_find {
        
        static class Uf {
            Map<String, String> parents = new HashMap<>();
            String getRoot(String child) {
                if (!parents.containsKey(child)) {
                    parents.put(child, child);
                    return child;
                }
                if (!parents.get(child).equals(child)) {
                    parents.put(child, getRoot(parents.get(child)));
                }
                return parents.get(child);
            }
            void union(String a, String b) {
                String root1 = getRoot(a), root2 = getRoot(b);
                if (root1.compareTo(root2) < 0) {
                    parents.put(root2, root1);
                } else {
                    parents.put(root1, root2);
                }
            }
        }
        
        public String[] trulyMostPopular(String[] names, String[] synonyms) {
            Uf uf = new Uf();
            Map<String, Integer> count = new HashMap<>();
            for (String pair : synonyms) {
                int coma = pair.indexOf(',');
                uf.union(pair.substring(1, coma), pair.substring(coma + 1, pair.length() - 1));
            }
            for (String name : names) {
                int par = name.indexOf('(');
                String name1 = name.substring(0, par);
                String root = uf.getRoot(name1);
                count.put(root, count.getOrDefault(root, 0) + Integer.parseInt(name.substring(par + 1, name.length() - 1)));
            }
            String[] res = new String[count.size()];
            int i = 0;
            for (Map.Entry<String, Integer> each : count.entrySet()) {
                res[i++] = each.getKey() + '(' + each.getValue() + ')';
            }
            return res;
        }
    }
    
    /**
     * 什么样的选手会写出这种代码？
     * 非常的傻屄，不得不说，很傻屄
     * */
    static class make_a_futile_effort {
        Pattern freqPattern = Pattern.compile("(\\w+)\\((\\d+)\\)");
        Pattern synoPattern = Pattern.compile("\\((\\w+),(\\w+)\\)");
    
        public String[] trulyMostPopular(String[] names, String[] synonyms) {
            Map<String, Integer> indexMap = new HashMap<>();
            Map<String, Integer> freqs = new HashMap<>();
            Map<String, Set<String>> synoMap = new HashMap<>();
        
            int idx = 0;
            for (String name : names) {
                Matcher matcher = freqPattern.matcher(name);
                matcher.matches();
                String realName = matcher.group(1);
                indexMap.put(realName, idx++);
                freqs.put(realName, Integer.parseInt(matcher.group(2)));
            }
        
            // 企图用一个循环把所有关系维护上可行吗？感觉上是可以的，实际上好像不大行
            for (String synonym : synonyms) {
                Matcher matcher = synoPattern.matcher(synonym);
                matcher.matches();
                String from = matcher.group(1), to = matcher.group(2);
                Set<String> name1 = synoMap.computeIfAbsent(from, k -> new HashSet<>());
                name1.add(to);
                name1.forEach(i -> synoMap.computeIfAbsent(i, k -> new HashSet<>()).add(from));
                Set<String> name2 = synoMap.computeIfAbsent(to, k -> new HashSet<>());
                name2.add(from);
                name2.forEach(i -> synoMap.computeIfAbsent(i, k -> new HashSet<>()).add(to));
            }
        
        
            Map<String, String> finalSynoMap = new HashMap<>();
            for (Map.Entry<String, Set<String>> next : synoMap.entrySet()) {
                String key = next.getKey();
                Set<String> synos = next.getValue();
                if (!indexMap.containsKey(key)) continue;
                int minIdx = indexMap.get(key);
                String minName = null;
                for (String syno : synos) {
                    if (!indexMap.containsKey(syno)) continue;
                    int t;
                    if ((t = indexMap.get(syno)) < minIdx) {
                        minIdx = t;
                        minName = syno;
                    }
                }
                if (!key.equals(minName)) finalSynoMap.put(key, minName);
                for (String syno : synos) {
                    if (!key.equals(syno)) finalSynoMap.put(syno, minName);
                }
            }
        
            Map<String, Integer> newFreq = new HashMap<>();
            Iterator<Map.Entry<String, Integer>> freqIt = freqs.entrySet().iterator();
            while (freqIt.hasNext()) {
                Map.Entry<String, Integer> next = freqIt.next();
                String name = next.getKey();
                int freq = next.getValue();
                if (finalSynoMap.containsKey(name)) {
                    String minName = finalSynoMap.get(name);
                    newFreq.put(minName, freqs.get(minName) + freq);
                    freqIt.remove();
                }
            }
        
            String[] res = new String[newFreq.size()];
            int i = 0;
            for (Map.Entry<String, Integer> each : newFreq.entrySet()) {
                res[i++] = each.getKey() + "(" + each.getValue() + ")";
            }
            return res;
        }
    }
}
